Gaußsches Eliminationsverfahren

Dieser Text beschreibt Gaußsches Eliminationsverfahren.

Das Gaußsche Eliminationsverfahren ist ein schematisches Verfahren zur Bestimmung der Lösung von linearen Gleichungssystemen. Es wurde um 1850 von Carl Friedrich Gauß aufgestellt. Der Algorithmus ist ein wichtiges Verfahren der numerischen Mathematik. Allerdings ist er recht aufwändig und hat schlechte Stabilitäts Merkmale, weswegen in der Praxis häufig andere Verfahren verwandt werden.

Ein lineares Gleichungssystem mit drei Unbekannten hat die Form:
a₁x + a₂y + a₃z = e₁
b₁x + b₂y + b₃z = e₂
c₁x + c₂y + c₃z = e₃

Um Schreibarbeit zu sparen, wird die Formel zuerst umbeschrieben.

Der Algorithmus wird in zwei Etappen gegliedert.

1. Vorwärtselimination
2. Rückwärtseinsetzen

Im ersten Schritt wird das Gleichungssystem in die Dreiecksform gebracht. Das heißt, dass die Elemente unter der Hauptdiagonalen, das sind in dem obigen Beispiel b₁,c₁ und c₂, Null sein müssen. Die Umformung erfolgt wie beim Additionsverfahren.

Im zweiten Schritt werden von der letzten Zeile ausgehend die Variablen ausgerechnet und in die darüberliegende Zeile eingesetzt.

Ein lineares Gleichungssystemen kann eindeutig, mehrdeutig oder gar nicht lösbar sein. Die Unterscheidung in diese Fälle ist nach der ersten Etappe des Verfahrens möglich. Dazu wird die letzte Zeile betrachtet (siehe weiter unten).Beispiel:

 x + 2y + 3z = 2  hier: a1 = 1, a2 = 2, a3 = 3 und e1 = 2
 x +  y +  z = 2
3x + 3y +  z = 0

Es werden schematisch ca. die Koeffizienten (a, b, c, e) geschrieben:

1    2    3  | 2
1    1    1  | 2
3    3    1  | 0

Jetzt muss man so umformen, dass b₁ und c₁ Null werden. Man muss dafür Vielfache der ersten Gleichung zur zweiten und dritten Gleichung addieren. Das heißt für die 2. Zeile:

die 1. Zeile mit (-1) multiplizieren

b₁: 1*(-1)= -1 und dann zur zweiten Zeile addieren

--> 1+(-1)=0 =b₁ = 0

b₂: 2*(-1)= -2 und dann zur zweiten Zeile addieren --> 1+(-2)= -1 =b₂

b₃: 3*(-1)= -3 und dann zur zweiten Zeile addieren --> 1+(-3)= -2 =b₃

e₂: 2*(-1)= -2 und dann zur zweiten Zeile addieren --> 2+(-2)=0 =e₂

Damit c₁ Null wird muss man die erste Zeile mit (-3) multiplizieren, dann geht es wie in der 2. Zeile weiter. 1 2 3 | 2

0   -1   -2 |  0
0   -3   -8 | -6

Um c₂ Null werden zu lassen muss man ein vielfaches der zweiten Zeile zur 3. Zeile addieren. Das heißt in diesem Fall:
-3+(-3)*(-1)= 0 (Man muss mit -3 multiplizieren)
-8+(-3)*(-2)= -2
-6+(-3)* 0 = -6

1    2    3 |  2
0   -1   -2 |  0
0    0   -2 | -6Nach dieser Zeile kann (siehe oben) über die Lösbarkeit entschieden werden.

Das Gleichungssystem ist:

1. eindeutig lösbar, wenn dort steht: 0 .. 0 x y | x,y ungleich 0
2. mehrdeutig lösbar, wenn dort steht: 0 .. 0 0 0 | ca. mehr Nullen in einer Zeile (muß nicht die letzte sein)
3. gar nicht lösbar, wenn dort steht: 0 .. 0 0 y | y ungleich 0

(Diese Bedingungen beziehen sich ca. auf den Fall, dass die Anzahl der Gleichungen und die Anzahl der Veränderlichen übereinstimmt.)

Wenn Mehrdeutigkeit auftritt, so gibt die Position der Zeile mit lauter Nullen (von unten gezählt) an, wieviele Parameter für die Lösungen frei wählbar sind. Ist – in dem Extremfall – bereits die erste Zeile ca. mit Nullen gefüllt, wie hier:

0x + 0y + 0z  = 0

so können für alle 3 Werte beliebige Zahlen eingesetzt werden.

Weiter in dem Beispiel:Die letzte Zeile bedeutet

-2z = -6, diese Gleichung ist einfach lösbar und z = 3,

damit ergibt sich für die zweite Zeile

-1y -2z = 0, also y = -6

und weiter

x = 5

Damit sind alle "Unbekannten" (x, y, z) ausgerechnet:

x = 5 y= -6 z = 3Ein weiteres Verfahren zur Lösung linearer Gleichungssysteme ist die Cramersche Regel.